package com.chuan.thinkingjava.algorithm;

import java.util.Arrays;

/**
 * @author Bowen
 * @version 1.0.0
 * @ClassName QuickSort.java
 * @Description 快排
 * @createTime 2020年12月15日 14:50:00
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arry = new int[]{34,1,5,64,13,64,3,6,86,24,4,6,2,74,25,7,56};
        sort(arry, 0, arry.length - 1);
        System.out.println(Arrays.toString(arry));
    }

    private static void sort(int[] arry, int low, int hight) {
        if (low >= hight) {
            return;
        }

        int p = arry[low]; //基值，选取第一起始位置
        int i = low; //前指针
        int j = hight; // 后指针

        while (i < j) {
            while (arry[j] >= p && i < j) {
                j --;
            }
            while (arry[i] <= p && i < j) {
                i ++;
            }

            int temp = arry[j];
            arry[j] = arry[i];
            arry[i] = temp;
        }

        arry[low] = arry[i];
        arry[i] = p;

        sort(arry, low, i - 1);
        sort(arry, j + 1, hight);
    }
}